package _11_整理题目._4_动态规划._子数组子矩阵;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/maximum-product-subarray/
 * https://leetcode-cn.com/problems/maximum-product-subarray/solution/cheng-ji-zui-da-zi-shu-zu-by-leetcode-solution/
 *
 * 给你一个整数数组 nums，请你找出数组中乘积最大的非空连续子数组
 * （该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
 * 测试用例的答案是一个 32-位 整数。
 * 子数组 是数组的连续子序列。
 *
 * 由于和最大子数组和 不一样，受正负号的影响，不具有最优子结构
 * 但是如果分开正负考虑，则具有最优子结构。
 *
 * 具体地，我们可以根据正负性进行分类讨论：
 * 考虑当前位置如果是一个负数的话，那么我们希望以它前一个位置结尾的某个段的积也是个负数，
 * 这样就可以负负得正，并且我们希望这个积尽可能「负得更多」，即尽可能小。
 * 如果当前位置是一个正数的话，我们更希望以它前一个位置结尾的某个段的积也是个正数，
 * 并且希望它尽可能地大。
 *
 * 维护一个 dpMax，dpMax[i] = Max(dpMax[i-1]*nums[i], dpMax[i-1]*nums[i], nums[i]);
 * 维护一个 dpMin，dpMin[i] = Min(dpMax[i-1]*nums[i], dpMax[i-1]*nums[i], nums[i]);
 */
public class _03_连续子数组的最大乘积 {

    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dpMax = Arrays.copyOf(nums, n);
        int[] dpMin = Arrays.copyOf(nums, n);
        // 求 dpMax 和 dpMin
        for (int i = 1; i < n; i++) {
            dpMax[i] = Math.max(dpMax[i-1]*nums[i], Math.max(dpMin[i-1]*nums[i], nums[i]));
            dpMin[i] = Math.min(dpMax[i-1]*nums[i], Math.min(dpMin[i-1]*nums[i], nums[i]));
        }
        int max = dpMax[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, dpMax[i]);
        }
        return max;
    }

    @Test
    public void main() {
        int[] nums = {5,6,-3,4,-3}; // 1080
        System.out.println(maxProduct(nums));
    }
}
